COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00014 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a31.tex[154,phy] \today\hfill}
\parskip 6pt

\bigskip
\noindent{\bf Midterm solutions.}
\parindent 0pt

\medskip
{\bf 1(A).} Proof No.~1.

Let $M=(\Sigma,Q↓M,S↓M,F↓M,T)$ be an NFA for~$L$. Define a nondeterministic
machine which runs in three phases:

\smallskip\disleft 20pt:
(1): Initialize relations $R$ and $R'$ to the identity $I↓{Q↓M}$.

\smallskip\disleft 20pt:
(2): Read the characters of $x$. On reading character~$b$, perform
$R:=T↓b\circ R$. When done, $R=T↓{\widehat{x}}$.

\smallskip\disleft 20pt:
(3): Read the characters of $y$. On reading character~$b$, perform
$R':=R'\circ T↓b$. When done, $R'=T↓y$. 
Accepting states are those where
$$S↓M\circ R'\circ R\circ F↓M\,.$$
The above machine accepts the desired set~$S$.

\smallskip
{\bf 1(A).} Proof No.~2.
Let $M$ be an NFA for $L$, and $\widehat{M}$ its dual. Let $M↓{ij}$ be like~$M$,
except that its only start state is~$q↓i$ and its only accepting state
is~$q↓j$; similarly for $\widehat{M}↓{ij}$. Then the composition
$\widehat{M}↓{kj}\circ M↓{ij}$ accepts strings~$xy$ such that~$\widehat{x}$
takes~$M$ from~$q↓k$ to~$q↓j$ and $y$ takes~$M$ from~$q↓i$ to~$q↓j$.
 Form the finite union, over all
$q↓i\in S↓M$, $q↓j\in Q↓M$, $q↓k\in F↓M$.

\smallskip
{\bf 1(A).} Proof No.~3.
Build a (finite) machine which decides nondeterministically when it passes
from reading~$x$ to reading~$y$. While reading~$x$, it keeps track of the
infix equivalence class of~$\widehat{x}$ (see 1(B));
since equivalence classes form a
finite semigroup, this requires a finite store. While reading~$y$, it
keeps track of the infix equivalence class of~$y$. Accepting states are
those where the concatenation of the two classes contains a string in~$L$.

\medskip
{\bf 1(B).} Proof No.~1.
(Infix equivalence.) Let $M$ read~$x$, keeping track of the infix equivalence
class of~$x$. For example, $M$~keeps track of the shortest~$y$ such that
$y\approx x$. On reading~$a$, it replaces $y$ by the shortest equivalent
of~$ya$. Accepting states are those for which $yy\in L$.

\smallskip
{\bf 1(B).} Proof No.~2.
(NFA construction.) Let $M$ be an NFA for~$L$. Define an NFA, which starts
by guessing states $q↓i\in S↓M$, $q↓j\in Q↓M$, $q↓k\in F↓M$. It then reads~$x$,
while simulating the cartesian product of machine $M↓{ij}$ with
machine~$M↓{jk}$.

\smallskip
{\bf 1(B).} Proof No.~3.
(Transition relations.) Define a DFA which keeps track of~$M$'s transition
relation~$R$ for~$x$. Accepting states are those where $S↓M\circ R↑2\circ F↓M$.

\medskip
{\bf 1(C).} Proof No.~1.
Let $M$ be an NFA for~$L$. Define a DFA which keeps track of the transition
relation~$R$ for~$x$. Accepting states are those where, for every $i≥0$,
$S↓M\circ R↑i\circ F↓M$.

\smallskip
{\bf 1(C).} Proof No.~2.
Define a DFA which keeps track of the infix equivalence class of~$x$.
At each new value of~$x$, it generates equivalence classes of~$x↑i$
($i=0,1,2,\ldots$) until a repetition occurs or a string not in~$L$
is found. The latter are the non-accepting states.

\medskip
{\bf 2.} Proof No.~1.
Let $L↓1$ and $L↓2$ both be the language $\{\,a↑i\mid i$ is not a perfect
square or $i≤1\,)$. 
Then the shuffle of~$L↓i$ and~$L↓2$ is~$a↑{\ast}$, which is regular.

\smallskip
{\bf 2.} Proof No.~2.
If $L↓1$ and $L↓2$ both contain $\epsilon$, then the shuffle of~$L↓1$
and~$L↓2$ contains both $L↓1$ and~$L↓2$. Let $L↓3$ be any non-regular
set, $L↓1=L↓3+\epsilon$, $L↓2={\rm complement}(L↓3)+\epsilon$. Then
the shuffle of~$L↓1$ and~$L↓2$ is~$\Sigma↑{\ast}$.

\medskip
{\bf 3(A).} PROGRAM is a legal prefix; END is not, so they are inequivalent.

\medskip
{\bf 3(B).} Neither END BEGIN nor END; BEGIN is a legal prefix, so the are
prefix equivalent. The former is illegal in some places where the latter
is legal, so they are infix inequivalent.

\medskip
{\bf 4.} Proof No.~1.
(For typographic reasons, I~use $≡$ as a synonym for~$\sim$.)
Clearly $a↑6\not\equiv a↑8$, $a↑4\not\equiv a↑6$. We deduce
$a↑3\not\equiv a↑5$, $a↑2\not\equiv a↑4$,
$a\not\equiv a↑3$, $\epsilon \not\equiv a↑2$. If it were true that
$a≡\epsilon$, we would have $a↑2=aa≡\epsilon a=a≡\epsilon$, absurd,
so $a\not\equiv\epsilon$. Similarly, if it were true that $a↑2≡a$, we
would have
$$a↑4=a↑2a↑2≡aa↑2=a↑2a≡aa=a↑2\,,$$
absurd. Then $\epsilon$, $a$, and $a↑2$ belong to distinct equivalence
classes corresponding to at least three distinct states. A~machine which
counts~$a$'s mod~3 and accepts if the count is not zero achieves this lower
bound.

\smallskip
{\bf 4.} Proof No.~2.
Any minimized DFA for $L$, upon reading a string of~$a$'s, will eventually
go into a cycle. If it enters the cycle before~$a↑4$, the cycle length
can't be~1 or~2 (why?), so must be $≥3$. If it doesn't enter the cycle
before~$a↑4$, there are at least five states entered.

\medskip
{\bf 5.} 
Remove inaccessible states. Initially partition the remaining states, 
putting together only those which give the same outputs on all one-character
inputs. Then iteratively refine the partition, putting together only those
which go into the same subsets on all one character inputs. The number of
classes is a bounded non-decreasing sequence of integers, so it stops;
an induction on string length shows the partition is the equivalence relation.

\medskip
{\bf 6.} 
An obvious construction achieves $n↓1\cdot n↓2$ states. By making $L↓1$
and~$L↓2$ embody sufficiently independent constraints, a~minimized
DFA will have to keep track of equivalence classes relative to both
$L↓1$ and~$L↓2$. Let $\Sigma=\{a,b\}$. Let $L↓1$ be the strings over~$\Sigma$
with a~multiple of $n↓1\;a$'s, and $L↓2$~the strings over~$\Sigma$
with a multiple
of~$n↓1\;b$'s. There are clearly $n↓1\cdot n↓2$ equivalence classes,
so a~minimized DFA needs that many states.

\medskip
{\bf 7.} 
To have $n$ prefix equivalence classes, the language must have an
$n$-state minimal~DFA. (E.g., it is~$(a↑n)↑{\ast}$.) To have $n↑n$~infix
equivalence classes, there must be a string for each possible transition
function. The easy way to accomplish that is to expand the input
alphabet, so that there is a character for each transition function.
A~much tougher problem: can it be done with a 2-character alphabet?
(Hint: look at $n=2$ and $n=3$.)

\medskip
{\bf 8.} 
The proof I had in mind is that the fixed-point theorem shows that
$$\eqalign{L↓S&=aL↓B∪bL↓A\cr
L↓A&=a∪aL↓S∪bL↓AL↓A\cr
L↓B&=b∪bL↓S∪aL↓BL↓B\,,\cr}$$
and by induction on lengths of strings, this solution is unique. Let
$L↓+$~be the strings with one more~$a$ than~$b$, $L↓-$~those with
one more~$b$ than~$a$, $L↓0$~those (other than~$\epsilon$) with equal
numbers of~$a$'s and~$b$'s. Then clearly
$$\eqalign{L↓0&=aL↓-∪bL↓+\cr
L↓+&=a∪aL↓0∪bL↓+L↓+\cr
L↓-&=b∪bL↓0∪aL↓-L↓-\,.\cr}$$
By the uniqueness, $L↓0=L↓S=L↓G$.


\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft November 13, 1984

\bye